package elementaryAlgorithm;

import java.awt.image.ImageProducer;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

/**
 * @author 郭辉
 * @className TODO
 * @description 130. 被围绕的区域
 * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
 *
 *
 * 示例 1：
 *
 *
 * 输入：board = [['X','X','X','X'],['X','O','O','X'],['X','X','O','X'],['X','O','X','X']]
 * 输出：[['X','X','X','X'],['X','X','X','X'],['X','X','X','X'],['X','O','X','X']]
 * 解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。
 * 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
 * 示例 2：
 *
 * 输入：board = [['X']]
 * 输出：[['X']]
 *
 *
 * 提示：
 *
 * m == board.length
 * n == board[i].length
 * 1 <= m, n <= 200
 * board[i][j] 为 'X' 或 'O'
 * 通过次数222,235提交次数480,945
 * @date 2023/4/6 17:24
 * @company 海康威视
 * @since 1.0.0
 */
public class Leet130 {
    //深度优先
    public void solvebfs(char[][] board) {
        if (board == null){
            return;
        }
        int row = 0;
        int col = 0;
        //上
        for (int i = 0; i < board[0].length; i++) {
            if (board[row][i] == 'O'){
                bfs(board,row,i);
            }
        }
        //下边
        row = board.length-1;
        for (int i = 0; i < board[0].length; i++) {
            if (board[row][i] == 'O'){
                bfs(board,row,i);
            }
        }
        //左边
        for (int i = 0; i < board.length; i++) {
            if (board[i][col] == 'O'){
                bfs(board,i,col);
            }
        }
        //右边
        col = board[0].length - 1;
        for (int i = 0; i < board.length; i++) {
            if (board[i][col] == 'O'){
                bfs(board,i,col);
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'A'){
                    board[i][j] = 'O';
                }else if (board[i][j] == 'O'){
                    board[i][j] = 'X';
                }else {
                    board[i][j] = 'X';
                }
            }
        }
    }

    //广度优先
    public void solvedfs(char[][] board) {
        if (board == null){
            return;
        }
        int row = 0;
        int col = 0;
        //上
        for (int i = 0; i < board[0].length; i++) {
            if (board[row][i] == 'O'){
                dfs(board,row,i);
            }
        }
        //下边
        row = board.length-1;
        for (int i = 0; i < board[0].length; i++) {
            if (board[row][i] == 'O'){
                dfs(board,row,i);
            }
        }
        //左边
        for (int i = 0; i < board.length; i++) {
            if (board[i][col] == 'O'){
                dfs(board,i,col);
            }
        }
        //右边
        col = board[0].length - 1;
        for (int i = 0; i < board.length; i++) {
            if (board[i][col] == 'O'){
                dfs(board,i,col);
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'A'){
                    board[i][j] = 'O';
                }else if (board[i][j] == 'O'){
                    board[i][j] = 'X';
                }else {
                    board[i][j] = 'X';
                }
            }
        }
    }

    //路径
    //选择
    //返回条件
    public void dfs(char[][]choose, int row, int col){
        //返回条件
        if (row < 0 || row> choose.length - 1 || col <0 || col > choose[0].length -1  || choose[row][col] == 'X' || choose[row][col] == 'A'){
            return;
        }
        //遍历选择
        /*
        * 上下左右四个节点
        *  */
        choose[row][col] = 'A';
        dfs(choose,row-1,col);
        dfs(choose,row+1,col);
        dfs(choose,row,col-1);
        dfs(choose,row,col+1);
    }


    //广度优先
    public void bfs(char[][]board,int row,int col){
        Queue<int[]>queue = new LinkedList<>();
        Set<int[]> visited = new HashSet<>();
        queue.add(new int[]{row,col});
        visited.add(new int[]{row,col});

        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] poll = queue.poll();
                board[poll[0]][poll[1]] = 'A';
                //上
                if (vaild(poll[0]-1, poll[1],board) && !visited.contains(new int[]{poll[0]-1, poll[1]}) ){
                    if (board[poll[0]-1][poll[1]] == 'O'){
                        queue.add(new int[]{poll[0]-1, poll[1]});
                        visited.add(new int[]{poll[0]-1, poll[1]});
                    }
                }
                //下
                if (vaild(poll[0]+1, poll[1],board) && !visited.contains(new int[]{poll[0]+1, poll[1]}) ){
                    if (board[poll[0]+1][poll[1]] == 'O'){
                        queue.add(new int[]{poll[0]+1, poll[1]});
                        visited.add(new int[]{poll[0]+1, poll[1]});
                    }
                }
                //左
                if (vaild(poll[0], poll[1]-1,board) && !visited.contains(new int[]{poll[0], poll[1] -1})){
                    if (board[poll[0]][poll[1]-1] == 'O'){
                        queue.add(new int[]{poll[0], poll[1]-1});
                        visited.add(new int[]{poll[0], poll[1]-1});
                    }
                }
                //右
                if (vaild(poll[0], poll[1]+1,board) && !visited.contains(new int[]{poll[0], poll[1] +1}) ){
                    if (board[poll[0]][poll[1]+1] == 'O'){
                        queue.add(new int[]{poll[0], poll[1]+1});
                        visited.add(new int[]{poll[0], poll[1]+1});
                    }
                }
            }
        }
        return;
    }

    public boolean vaild(int row, int  col,char[][]board ){
        if (row < 0 || col < 0 || row > board.length -1 || col > board[0].length - 1 || board[row][col] =='X'){
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        char[][] board = {
                {'X','X','X','X'},
                {'X','O','O','X'},
                {'X','X','O','X'},
                {'X','O','X','X'}};

        char[][]board2 = {
                {'X','O','X','O','X','O'},
                {'O','X','O','X','O','X'},
                {'X','O','X','O','X','O'},
                {'O','X','O','X','O','X'}
        };
        
        char[][]board3 = {
                {'O','X','O','O','O','X'},
                {'O','O','X','X','X','O'},
                {'X','X','X','X','X','O'},
                {'O','O','O','O','X','X'},
                {'X','X','O','O','X','O'},
                {'O','O','X','X','X','X'}
        };
        
        Leet130 leet130 = new Leet130();
        leet130.solvebfs(board3);
        System.out.println(board);
    }
}

